package one.chapter_3;

import one.chapter_1.queue.LinkedQueue;
import one.chapter_1.queue.Queue;

public class BinarySearchST<Key extends Comparable<Key>, Value> implements SeqST<Key, Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;

    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Comparable[capacity];
    }


    @Override
    public Key min() {
        return keys[0];
    }

    @Override
    public Key max() {
        return keys[N - 1];
    }

    /**
     * 小于等于key的最大键
     * @param key
     * @return
     */
    @Override
    public Key floor(Key key) {
        int i= rank(key);
        if (contains(key)){
            return keys[i];
        }else {
            if (i==0){
                return null;
            }
            return keys[i-1];
        }
    }
    /**
     * 大于等于key的最大键
     * @param key
     * @return
     */
    @Override
    public Key ceiling(Key key) {
        int i = rank(key);
        return keys[i];
    }

    /**
     * 小于key的键的数量
     * @param key
     * @return
     */
    @Override
    public int rank(Key key) {

        int lo = 0;
        int hi = N - 1;
        while (lo <= hi) {

            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) {
                hi = mid - 1;
            } else if (cmp > 0) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return lo;
    }

    /**
     * 递归版本
     *
     * @param key
     * @param lo
     * @param hi
     * @return
     */
    private int rank(Key key, int lo, int hi) {
        if (hi < lo) return lo;
        //使用二分查找
        int mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) {
            return rank(key, lo, mid - 1);
        } else if (cmp > 0) {
            return rank(key, mid + 1, hi);
        } else {
            return mid;
        }


    }

    @Override
    public Key select(int k) {
        return keys[k];
    }

    @Override
    public void deleteMin() {

    }

    @Override
    public void deleteMax() {

    }

    @Override
    public int size(Key lo, Key hi) {
        return 0;
    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi) {

        Queue<Key> q = new LinkedQueue<>();
        for (int i = rank(lo); i < rank(hi); i++) {
            q.enqueue(keys[i]);
        }
        if (contains(hi)){
            q.enqueue(keys[rank(hi)]);
        }

        return q;
    }

    @Override
    public void put(Key key, Value value) {

        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            vals[i] = value;
            return;
        }

        for (int j = N; j > i; j++) {
            keys[j] = keys[j - 1];
            vals[j] = vals[j - 1];
        }
        keys[i] = key;
        vals[i] = value;
        N++;
    }

    @Override
    public Value get(Key key) {
        if (isEmpty()) return null;
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            return vals[i];
        }

        return null;
    }

    @Override
    public void delete(Key key) {

    }

    @Override
    public Iterable<Key> keys() {
        return keys(keys[0],keys[N-1]);
    }

    @Override
    public boolean contains(Key key) {
       return get(key)!=null;

    }

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public int size() {
        return N;
    }


}
